// 题目要求：
// 给一个整数 n，表示有 n 种活动
// 给一组 groups，每个 group 里面有两个活动，表示完成了 group[1] 才能完成 group[0]
// 请判断是否能完成考核，能完成返回完成活动的顺序，不能完成返回空

// 解题思路：
// 经典的拓扑排序问题
// 1. 建立入度信息数组和邻接表，遍历 groups，统计入度信息和边的信息
// 2. 将入度为 0 的活动加入到队列中，入度为 0 就表示活动没有前置活动，是能够最先开展的活动
// 3. 拓扑排序
//    将队列中的活动弹出，加入到返回结果中；
//    将该活动的后置活动的入度减 1，如果入度减到 0 了，入队，表示这个活动也可以开展了
// 4. 如果最终返回结果中包含了所有的活动，就表示能够完成活动，如果不包含，就表示存在矛盾，不能完成


import java.util.*;

public class TopoSort2 {
    public ArrayList<Integer> findOrder (int numProject, ArrayList<ArrayList<Integer>> groups) {
        int[] in = new int[numProject];
        Map<Integer, List<Integer>> edges = new HashMap<>();
        int n = groups.size();

        // 1. 建图
        for(int i = 0; i < n; i++){
            int first = groups.get(i).get(1);
            int second = groups.get(i).get(0);

            in[second]++;
            if(!edges.containsKey(first)){
                edges.put(first, new ArrayList<>());
            }
            edges.get(first).add(second);
        }

        // 2. 入度为 0 的点入队
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numProject; i++){
            if(in[i] == 0){
                queue.offer(i);
            }
        }

        // 3. 拓扑排序
        ArrayList<Integer> ret = new ArrayList<>();
        while(!queue.isEmpty()){
            int t = queue.poll();
            ret.add(t);
            if(edges.containsKey(t)){
                List<Integer> edge = edges.get(t);
                for(int x : edge){
                    in[x]--;
                    if(in[x] == 0){
                        queue.offer(x);
                    }
                }
            }
        }

        return ret.size() == numProject ? ret : new ArrayList<>();
    }
}
